package test.n00200;


import java.util.*;

public class Problem00300 {
    public static void main(String[] args) {
        //println("barfoothefoobarman", Arrays.asList("foo", "bar"));
        println("wordgoodgoodgoodbestword", Arrays.asList("word", "good", "best", "good"));
    }

    public static void println(String s, List<String> words) {
        Solution ss = new Solution();
        System.out.println(s + "," + words + "," + ss.findSubstring(s, words.toArray(new String[0])));
    }

    private static class Solution {
        /**
         * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
         *
         * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
         *
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         * 解题思路:
         * 利用 hash 相同的方式比较两个map是否相等(以下算法不适合words长度不相等情况)
         *
         * @param s
         * @param words
         * @return
         */
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> result = new ArrayList<>();
            int wordsSize = words.length;
            if (s.length() == 0 || words.length == 0) {
                return result;
            }
            Map<String, Integer> map = new HashMap<>();
            for (String w : words) {
                map.put(w, map.getOrDefault(w, 0) + 1);
            }

            int oneWordLen = words[0].length();
            int allLen = wordsSize * oneWordLen;

            for (int i = 0; i < s.length() - allLen + 1; i++) {
                String str = s.substring(i, i + allLen);

                Map<String, Integer> tMap = new HashMap<>();
                for (int j = 0; j < wordsSize; j++) {
                    String t = str.substring(j * oneWordLen, (j + 1) * oneWordLen);
                    tMap.put(t, tMap.getOrDefault(t, 0) + 1);
                }

                if (map.equals(tMap)) {
                    result.add(i);
                }
            }
            return result;
        }
    }
}
